package com.gayatri.sort;

/**
 * For HeapSort heapify function gets the the max value from the array at the
 * top.
 * 
 * @author Gayathri
 * 
 */
public class HeapSort extends Sort {

	HeapSort(Integer[] numbers) {
		super(numbers, false);
	}

	@Override
	public void sort() {
		int n = numbers.length - 1;
		int i = n / 2;
		// We run heapify from the middle of the array to the initial position
		// This bottom up approach ensures that the values form a correct heap
		// from the leaves towards the root.
		while (i >= 0) {
			heapify(numbers, i, n);
			i--;
		}

		// We swap the max value at the top of the heap and exchange it with the
		// end of the array
		// We then run heapify on the rest of the array from 0 till the element
		// before the just exchanged.
		for (int j = 1; j <= n; j++) {
			swap(numbers, 0, n - j + 1);
			heapify(numbers, 0, n - j);
		}
	}

	private void heapify(Integer[] numbers, int i, int n) {
		int left_child;
		int right_child;
		int max_child;

		print();

		System.out.println("Parent id is : " + i);
		left_child = 2 * i;
		System.out.println("Left child is : " + left_child);
		if (left_child <= n) {
			right_child = left_child + 1;
			System.out.println("Right child is : " + right_child);
			if (right_child <= n && numbers[left_child] < numbers[right_child]) {
				max_child = right_child;
			} else {
				max_child = left_child;
			}

			if (numbers[i] < numbers[max_child]) {
				System.out
						.println("Swapping the current parent with the max child : "
								+ max_child);
				swap(numbers, i, max_child);
				heapify(numbers, max_child, n);
			}
		}
		iterations++;
	}

	@Override
	public int getExpectedIterations() {
		return 0;
	}

}
